package hiho.ku._1158;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static boolean[] notPrime = new boolean[500001];

	public static void main(String[] args) {
		for (int i = 2; i < 500001; i++)
			if (!notPrime[i]) {
				int j = i * 2;
				while (j < 500001) {
					notPrime[j] = true;
					j += i;
				}
			}

		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for (int i = 1; i <= t; i++) {
			System.out.print("Case #" + i + ": ");
			run(in);
		}
	}

	private static void run(Scanner in) {
		int n = in.nextInt();
		int[] nums = new int[n];
		for (int i = 0; i < n; i++)
			nums[i] = in.nextInt();
		Arrays.sort(nums);
		List<List<Integer>> map = new ArrayList<List<Integer>>();
		List<Integer> left = new ArrayList<Integer>();
		List<Integer> right = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			int j = 0;
			for (; j < left.size(); j++)
				if (nums[i] % left.get(j) == 0
						&& !notPrime[nums[i] / left.get(j)])
					break;
			if (j < left.size()) {
				for (; j < left.size(); j++)
					if (nums[i] % left.get(j) == 0
							&& !notPrime[nums[i] / left.get(j)])
						map.get(j).add(right.size());
				right.add(nums[i]);
			} else {
				left.add(nums[i]);
				List<Integer> tmp = new ArrayList<Integer>();
				for (j = 0; j < right.size(); j++)
					if (nums[i] % right.get(j) == 0 && !notPrime[nums[i] / right.get(j)])
						tmp.add(j);
				map.add(tmp);
			}
		}

		int[] mark = new int[right.size()];
		for (int i = 0; i < right.size(); i++)
			mark[i] = -1;
		int ans = 0;
		for (int i = 0; i < map.size(); i++) {
			boolean[] visited = new boolean[right.size()];
			if (find(i, map, mark, visited))
				ans++;
		}
		System.out.println(n - ans);
	}

	private static boolean find(int now, List<List<Integer>> map, int[] mark,
			boolean[] visited) {
		List<Integer> kids = map.get(now);
		for (int i = 0; i < kids.size(); i++) {
			int kid = kids.get(i);
			if (!visited[kid]) {
				visited[kid] = true;
				if (mark[kid] < 0 || find(mark[kid], map, mark, visited)) {
					mark[kid] = now;
					return true;
				}
			}
		}
		return false;
	}

}
